package leetcode.editor.cn1;

import java.util.HashMap;
import java.util.Map;

/**
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * <p>
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 */
public class NthUglyNumberLcof {

    public static void main(String[] args) {
        Solution solution = new NthUglyNumberLcof().new Solution();
        System.out.println(solution.nthUglyNumber(10));
    }


    class Solution {
        private Map<Integer, Integer> map = new HashMap<>();

        public int nthUglyNumber(int n) {
            if (n <= 0)
                return 0;
            int a = 0, b = 0, c = 0;
            int[] dp = new int[n];
            dp[0] = 1;
            for (int j = 1; j < n; j++) {
                // 那到底是取的哪一个
                dp[j] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c]*5);
                // 如何更新a, b, c的值
                if (dp[j] % 2 == 0) a = a + 1;
                if (dp[j] % 3 == 0) b++;
                if (dp[j] % 5 == 0) c++;
            }
            return dp[n - 1];
        }

        public boolean isNthUglyNumber(int n) {
            if (n == 1 || n == 2 || n == 3 || n == 5)
                return true;
            if (map.containsKey(n))
                return true;
            boolean res = false;
            if (n % 2 == 0) {
                if (isNthUglyNumber(n / 2)) {
                    map.put(n, 1);
                    res = true;
                }
            } else if (n % 3 == 0) {
                if (isNthUglyNumber(n / 3)) {
                    map.put(n, 1);
                    res = true;
                }
            } else if (n % 5 == 0) {
                if (isNthUglyNumber(n / 5)) {
                    map.put(n, 1);
                    res = true;
                }
            } else return false;

//            while (n != 1) {
//                if (n % 2 == 0) {
//                    n = n / 2;
//                } else if (n % 3 == 0) {
//                    n = n / 3;
//                } else if (n % 5 == 0) {
//                    n = n / 5;
//                } else {
//                    return false;
//                }
//            }
//            map.put(n, 1);
//            return true;
            return res;
        }
    }
}
